The present invention is directed to image processing and particularly to methods and apparatus for halftoning.
Image data are typically taken and stored in formats that are not well suited to use by image-presentation devices such as printers. A digitally stored or processed gray-scale image typically consists of a fine-value-quantization--say, 8-bit--scalar pixel value associated with each a large number of picture elements ("pixels") of which the image consists. Digital color images are similar, with the exception that the pixel value is a vector rather than a scalar, and a similarly fine-quantization quantity represents each of the vector's color components. The color image can be thought of as consisting of a plurality of image components, each of which is a "gray-scale" image represented by a different component of every vector pixel value. So much of the following discussion's reference to gray scales is equally applicable to values of individual image components.
Consider the case of an 8-bit-per pixel digital image. A pixel can have any gray value between 0, for completely white, and 255 (=2.sup.8 -1), for completely black. Actually, the meaning in the stored image is often just the reverse--i.e., zero represents total black and 255 represents completely white. But when the imaging-presenting mechanism is one like a printer, in which an increase in the applied amount of the imaging agent, i.e., ink, results in a reduction in image brightness, the image data are usually converted to complementary values during the image-presentation process. The discussion that follows will be presented in terms of such "complementary" values--i.e., a higher value will mean a darker image--but the principles apply equally to positive-color presentation such as that which occurs in a cathode-ray tube, in which the image medium (the screen) is dark until it is acted on by the imaging medium (an electron beam).
With so many possible gray values, such images arc often referred to as "continuous-tone" images, even though the possible values differ from each other by finite non-zero amounts. In contrast, the typical printer can render any single pixel only completely white or completely black: the continuous-tone values at any given pixel are only 0 and 255. Some printers are capable of somewhat finer value quantization, but the quantizations of which even those are capable are almost always coarser than that of the original image.
Now, if the continuous-tone image has a uniform pixel value throughout a region, an illusion of the intended gray value can be achieved in the printed image by alternating black and white pixels throughout that uniform-value region in a ratio that corresponds to the intended gray level. Of course, most images of interest have regions whose pixel values are not uniform, but techniques of achieving the same effect in such varying regions have been developed. Such techniques are referred to as digital halftoning.
The general principles of digital halftoning are well known. One, relatively fast way to perform halftoning is known as "ordered dither." This involves comparing pixel values with respective threshold values of a "dither matrix." To make the description more concrete, let us assume that the dither-matrix size is 128.times.128 and that the printer output is binary, i.e., only completely white or completely black at any single pixel. The image to be halftoned is divided into corresponding-size subregions, i.e., each subregion of the area to be printed is 128 pixel widths wide and 128 pixel heights high. A dithering process involves conceptually laying a copy of the dither matrix over each such subregion so that each pixel is associated with a respective dither threshold. If the image value at a given pixel exceeds that pixel's dither threshold, then the pixel is printed completely black: it receives an ink dot. Otherwise, it is printed completely white: it receives no ink. So the dither-operation output for each pixel is a binary indication of whether that pixel will receive an ink dot. For printers that are capable of multi-level operation, the process is somewhat different: the choice is between the two quantization levels whose continuous-tone equivalents are closest to the input continuous-tone value, and the threshold is compared with the difference between the continuous-tone value and lower of those continuous-tone equivalents.
Another general approach is referred to as "error diffusion." This approach, too, also involves a threshold comparison. But ordered dither requires that the dither-matrix values be distributed evenly throughout the continuous-tone range so that the number of pixels where the continuous-tone value exceeds the corresponding dither threshold in a uniform-value region is roughly proportional to that uniform value. The error-diffusion approach can--but does not necessarily have to--use only a single threshold, because the value with which the threshold is compared is a combination of the continuous-tone value for that pixel and various percentages of the quantization errors that have resulted from halftoning at various neighbor pixels. If the continuous-tone range is from zero to 255, then a pixel that receives a dot is actually printed at a value of 255, so there is an error of -12 at that pixel if the continuous-tone input was 243. This error is divided in accordance with an error-diffusion "kernel" among the pixel's neighbors that have not yet been half-toned, and the thresholds at those pixels are compared with those pixels'values adjusted by the errors that their neighbors thus contribute.
Although these methods are simple in principle, so applying them as to achieve a high-quality result requires considerable effort. The various threshold values in a dither matrix, for instance, must be distributed very evenly about the matrix if disturbing visual effects are to be suppressed as well as possible, and achieving such an even distribution in a dither matrix large enough to provide the desired apparent value quantization at the same time is not at all trivial Even when the desired even distribution is achieved, light and midtone regions tend to be afflicted with visual effects having the periodicity with which the dither matrix "tiles" the image.
The error-diffusion approach is less subject to such periodic effects, but it tends to introduce its own, "worming" effects, particularly in light regions. Moreover, the degree to which such effects can occur in any particular type of printer depends greatly on the particular error-diffusion kernel employed.
Given the demand for printer-generated images of increasingly high quality, printers' mechanical and electrical characteristics have been developed rapidly in recent years, and new printer designs have accordingly occurred at a rapid pace. This presents the need, for each one, to find the combination of halftone techniques and parameters that will fit each new printer well enough to meet the exacting image-quality demands imposed on it. As the required quality has increased, so has the amount of experimentation and design effort that this task requires.
Moreover, the design burden is affected not only by quality-requirement increases is but also by increases in the versatility that some new printers need. To provide finer value quantization, for instance, some printers can employ cartridges that provide inks of more than one darkness for a color component. Such a cartridge may afford the capability of depositing not only ordinary, dark cyan and magenta but also lighter, "photo" cyan and magenta, and doing so typically involves multi-level halftoning. But such a printer must also be able to use one-ink-per-color-component cartridges, so it must also be capable of performing binary halftoning for cyan and magenta. This choice therefore multiplies the halftoning-strategy design effort.
But it is not the only complication. Another is pixel-geometry choice. Printer technology has advanced to the point where the number of pixels into which a small space on the print medium is divided often significantly exceeds a given job's required spatial resolution, and the computation required to process so many pixels can slow the printing process undesirably. To avoid such unnecessary processing, some printers provide a print-quality selection, which permits the user to choose among different spatial-resolution settings, and this can affect pixel geometry. If each pixel in one column is aligned horizontally with a corresponding pixel in an adjacent column and the distance between adjacent pixel rows is the twice the distance between adjacent pixel columns, the pixel geometry is rectangular with an aspect ratio of two. When the user chooses a coarser resolution, the printer may take alternate pixel columns out of service, in which case the pixel geometry becomes square. Or the printer may adopt a checkerboard geometry by removing even-numbered pixels from even-numbered rows and odd-numbered pixels from odd-numbered rows. But a halftoning strategy that works well for the rectangular geometry may not be well suited to be square geometry, and a strategy that works well for the checkerboard geometry may not work well on either of the other two.
All of these factors combine to slow the design process and complicate printer-driver software.